The general problem of dividing property rationally and fairly among two, or more, claimants has been the subject of folklore, biblical stories, and history. A variety of procedures has been extensively written upon by economists, political scientists, mathematicians, and others.
The best-known, and most widely practiced, procedure for two persons is that one divides and the other chooses. For example, to divide a cake, Mary will cut the cake into two pieces, and John will then select which piece he wants, i.e., "divide-and-choose."
Applications of divide-and-choose span about five millennia, from biblical accounts of Abraham and Lot using this procedure to divide land to the recent Law of the Sea Treaty that reserves parcels of seabed for future mining operations by developing countries (developed countries do the "dividing"). The qualities that make this two-person procedure seem both workable and fair have been explicitly set forth by the inventors and others. They include the following:
1. The procedure is conceptually simple, with little reliance on any outside arbitrator or referee. Satisfaction with a fair-division scheme relies, in part, on a feeling that the process (i.e., the step-by-step mechanics leading to the allocation) is fair, as well as the product (i.e., the actual allocation).
2. The procedure is envy-free. That is, neither of the two parties will envy the other in the sense of wishing he or she had the other's share. For two people, this is equivalent to saying that each party thinks he receives at least half the total value in his or her own eyes.
Divide-and-choose, however, also has its drawbacks:
1. It is limited to two people. The mathematical problem of extending this procedure to a constructive one that is envy-free and works for any number of parties was open for over 30 years. It was recently solved by the present inventors; see Brams and Taylor, "An Envy-Free Cake-Division Protocol," American Mathematical Monthly. Vol. #1, No. 1, Jan. 1995, pp. 9-18.
2. The resulting allocation need not be efficient. That is, there may be some other allocation that is strictly better for both parties.
3. Although divide-and-choose prevents envy for what the other party receives, the resulting allocation need not be equitable. That is, one party may feel that he received only 60% of the value while knowing that the other party feels that she received 90% of the value. Thus, while neither will envy the other in the sense of wishing to trade, the former will envy the latter's "happiness" (90% bringing more happiness than 60%).
With regard to drawback 1 (the limitation to two people), the procedure considered, prior to this invention, to be the best for obtaining a fair division of a collection of goods (items), when each good is itself non-divisible (indivisible), is called "Knaster's procedure of sealed bids" or "Knaster's procedure." Each of the parties (players) submits sealed bids for each item, for example, to an impartial mediator who administers the procedure. The party who submits the highest bid is awarded the item. However, after the auction is over, some of the money bid for items is divided up among the parties. The procedure requires that each party has money.
The Knaster procedure is illustrated in Table 1 below. There are three parties (Bob, Carol, and Ted) and 4 items A,B,C,D listed in Table 1, for example, a boat, a car, a house lot, and a painting. The amount listed in Table 1 for each party and each item is the amount that that party has bid, in a sealed bid, for that item.
TABLE 1 ______________________________________ Party Bob Carol Ted ______________________________________ Valuation Item A $10,000 $4,000 $7,000 Item B 2,000 1,000 4,000 Item C 500 1,500 2,000 Item D 800 2,000 1,000 Total valuation 13,300 8,500 14,000 Items received A D B,C Value received 10,000 2,000 6,000 Initial fair share 4,433 2,833 4,667 Difference 5,567 -833 1,333 (initial excess/deficit) Share of surplus 2,022 2,022 2,022 Adjusted fair share 6,455 4,855 6,689 Final settlement A - 3,545 D + 2,855 B,C + 689 ______________________________________
Each party has bid a different amount (valuation) for each item, and the total of each party's bids is the total valuation. Each party gets the item for which he, or she, was high bidder; their winning bid is considered the valuation of that item. The "initial fair share" is the party's total valuation divided by the number of parties. For example, Bob's total valuation is $13,300; because there are 3 parties his initial fair share is $4,433. The difference between his value for the item (A) he receives ($10,000) and his initial fair share is $5,567.
These differences for all parties are summed algebraically: $5,567-$833+$1,333=$6,067, which is called the surplus. Each party is assigned one-third of the surplus, i.e., $2,022, which is added to its initial fair share, i.e., Bob's $4,433+$2,022=$6,455, which is his "adjusted fair share." This, in turn, is added (or subtracted) from the valuation of the item he, or she, received, i.e., Bob received item A valued at $10,000, and his adjusted fair share is $6,455 so he has a "final excess" of $10,000-$6,455=$3,545. Bob contributes, in money, this excess to the other parties, with Carol receiving $2,855 and Ted $689.
Knaster's procedure does guarantee envy-freeness in two-person situations but not if there are three or more parties. However, the Knaster procedure requires that the parties have the cash to pay for a final settlement. In many situations, including divorces, one or more parties do not have, and cannot borrow, sufficient money to implement the Knaster procedure.